#include <iostream>
#include <stdio.h>
#include <assert.h>
#include <stack>

namespace Y190614_exam_02_3_3_Reversing_Linked_List
{
using namespace std;

struct DataNode {
	int address;
	int data;
	int next;
};

typedef struct LNode* List;
typedef List LPosition;
struct LNode {
	DataNode data;
	List next;
};

typedef struct SNode* Stack;
struct SNode {
	LPosition data;
	Stack next;
};

void dump_array(LPosition p, int N) {
	LPosition p2;
	for (int i = 0; i < N - 1; ++i) {
		p2 = p + 1;
		printf("%05d %d %05d\n", p->data.address, p->data.data, p2->data.address);
		++p;
	}
	printf("%05d %d -1\n", p->data.address, p->data.data);
}

void dump_list(LPosition p) {
	while(p) {
		if (p->next)
			printf("%05d %d %05d\n", p->data.address, p->data.data, p->next->data.address);
		else
			printf("%05d %d -1\n", p->data.address, p->data.data);
		p = p->next;
	}
}

List read_input(int N) {
	int address, data, next;
	assert(N > 0);
	List values = (List)malloc(N * sizeof(struct LNode));
	LPosition p = values;
	int i = N;
	while (i--) {
		std::cin >> address >> data >> next;
		DataNode dp;
		dp.address = address;
		dp.data = data;
		dp.next = next;
		p->data = dp;
		p->next = NULL;
		++p;
	}
	return values;
}

LPosition list_find(List L, int N, int address) {
	LPosition p = L;
	for (int i = 0; i < N; ++i)
	{
		if (p->data.address == address)
			return p;
		++p;
	}
	return NULL;
}

List sort_data(List datas, int N, int first) {
	List root = NULL;
	LPosition p = NULL;
	LPosition s = NULL;
	while (first != -1) {
		s = list_find(datas, N, first);
		if (p) {
			s->next = NULL;
			p->next = s;
			p = s;
		}
		else {
			root = s;
			p = root;
		}
		first = s->data.next;
	}
	return root;
}

List KN_reverse(List root, int K, int N) {
	if (K <= 1 || N <= 1)
		return root;
	LPosition p = root;
	LPosition first = NULL;
	LPosition rear = NULL;

	for (int i = 0; i < N - K + 1; i += K) {
		stack<LPosition> stkPosition;
		for (int j = 0; j < K; ++j) {
			stkPosition.push(p);
			p = p->next;
		}
		if (first == NULL) {
			first = stkPosition.top();
			stkPosition.pop();
			rear = first;
		}
		while (!stkPosition.empty()) {
			rear->next = stkPosition.top();
			stkPosition.pop();
			rear = rear->next;
			rear->next = NULL;
		}
	}

	if (p)
		rear->next = p;

	return first;
}


int main()
{
	int first, N, K;
	cin >> first >> N >> K;
	List L = read_input(N);
	List root = sort_data(L, N, first);
	List reversed_list = KN_reverse(root, K, N);
	dump_list(reversed_list);
	free(L);
	return 0;
}
}

int main_Y190614_exam_02_3_3_Reversing_Linked_List()
{
	return Y190614_exam_02_3_3_Reversing_Linked_List::main();
}